#include <iostream>
#include <vector>
#include <functional>
using namespace std;

function<void(vector<int> &)> output = [](vector<int> &arr) -> void
{
    int length = arr.size();
    for (int i = 0; i < length; ++i)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
};

function<void(vector<int> &, int, int)> swapInVector = [](vector<int> &arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

void quickSort(vector<int> &arr, int left, int right)
{
    if (left >= right)
        return;
    int i = left, j = right;
    while (i < j)
    {
        while (i < j && arr[j] >= arr[left])
            j--;
        while (i < j && arr[i] <= arr[left])
            i++;
        swapInVector(arr, i, j);
    }
    swapInVector(arr, i, left);
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

void qSort(vector<int> &arr, int left, int right);
int partition(vector<int> &arr, int left, int right);
void quickSort_2(vector<int> &arr);

void qSort(vector<int> &arr, int left, int right)
{
    if (left >= right)
        return;
    int mid = partition(arr, left, right);
    qSort(arr, left, mid - 1);
    qSort(arr, mid + 1, right);
}

int partition(vector<int> &arr, int left, int right)
{
    int sentry = arr[left];
    int i = left + 1, j = right;
    while (i < j)
    {
        while (i < j && arr[i] <= sentry)
            i++;
        if (i != j)
        {
            swapInVector(arr, i, j);
            j--;
        }
    }
    if (i == j && arr[j] > sentry)
        j--;
    if (j != left)
        swapInVector(arr, left, j);
    return j;
}

void quickSort_2(vector<int> &arr)
{
    qSort(arr, 0, arr.size() - 1);
}

int main()
{
    vector<int> arr = {6, 2, 1, 3, 5, 4, 9, 7, 5, 4, 11, 2, 9, 4, 7, 3, 8, 10};

    vector<int> temp(arr);
    output(temp);
    quickSort(temp, 0, temp.size() - 1);
    output(temp);

    temp = arr;
    output(temp);
    quickSort_2(temp);
    output(temp);

    return 0;
}
